2328. Степенные числа

Число n называется степенным, если его можно представить в виде степени некоторого натурального числа, возведённого хотя бы во вторую степень.

· Например, 4 степенное число, так как 4 = 2².

· Число 27 также степенное, так как 27 = 3³.

· Однако 28 не является степенным числом.

Определите, какие из заданных чисел являются степенными.

Вход. Первая строка содержит количество чисел n (1 ≤ n ≤ 10). Во второй строке записаны n целых чисел, каждое из которых больше 1 и меньше 10⁹.

Выход. Выведите n строк. В i-й строке выведите “YES”, если i-е число является степенным, и “NO” в противном случае.

Пример входа	Пример выхода
2 27 28	YES NO

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

Пусть n – степенное число. Тогда существуют такие натуральные i и k, что i^k = n. Переберем значение i = 2, 3, 4, …, . Для каждого значения i переберем его степени i, i², i³, …, i^k до тех пор пока i^k ≤ n.

Если найдутся такие i и k, что i^k = n, то число n является степенным

Реализация алгоритма

Функция Degree определяет, является ли число n степенным.

int Degree(long long n)

{

long long i, j;

Перебираем i = 2, 3, 4, …, .

for (i = 2; i <= sqrt(n); i++)

{

j = i * i;

Перебираем j = i, i², i³, … .

while (j <= n)

{

Если существует такое k, что j = i^k = n, то число n является степенным.

if (j == n) return 1;

j *= i;

}

}

Число n не является степенным.

return 0;

}

Основная часть программы. Читаем количество тестов tests.

scanf("%d", &tests);

while (tests--)

{

Читаем входное число n.

scanf("%d", &n);

Определяем, является ли число n степенным. Выводим ответ.

if (Degree(n)) printf("YES\n");

else printf("NO\n");

}

Python реализация

import math

Функция is_power определяет, является ли число n степенным.

def is_power(n):

Перебираем i = 2, 3, 4, …, .

for i in range(2, int(math.sqrt(n)) + 1):

j = i * i

Перебираем j = i, i², i³, … .

while j <= n:

Если существует такое k, что j = i^k = n, то число n является степенным.

if j == n:

return True

j *= i

Число n не является степенным.

return False

Основная часть программы. Читаем входные данные.

tests = int(input())

lst = list(map(int, input().split()))

for n in lst:

Определяем, является ли число n степенным. Выводим ответ.

print("YES" if is_power(n) else "NO")